package com.xyhuo.leetcode.january;

/**
 * 买卖股票的最佳时机Ⅱ
 * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
 *
 * @time 2024/1/12
 */
public class MaxProfitSecond {

    public int maxProfit(int[] prices) {
        int[] dp = new int[prices.length];
        for (int i = 1; i < prices.length; i++) {
            int val = 0;
            for (int j = 0; j < i; j++) {
                if (prices[j] < prices[i]) {
                    int index = j - 1;
                    int max = 0;
                    while (index >= 0) {
                        if (dp[index] > max) {
                            max = dp[index];
                        }
                        index--;
                    }
                    int tmp = prices[i] - prices[j] + max;
                    if (tmp > val) {
                        val = tmp;
                    }
                }
            }
            dp[i] = val;
        }
        int ans = 0;
        for (int i = 0; i < prices.length; i++) {
            if (dp[i] > ans) {
                ans = dp[i];
            }
        }
        return ans;
    }


}
